package main.leetcode.primary.from001to100;

/**
 * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
 *
 * <p>'.' 匹配任意单个字符； '*' 匹配零个或多个前面的那一个元素
 *
 * <p>所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
 *
 * <p>说明:
 *
 * <p>s 可能为空，且只包含从 a-z 的小写字母. p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/regular-expression-matching
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex10 {
    public static void main(String[] args) {
        String s = "aa";
        String p = "a*";
        System.out.println(isMatch2(s, p));
    }

    // 动态规划
    public static boolean isMatch1(String s, String p) {
        if (p.isEmpty()) return s.isEmpty();

        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1]; // s 的前 i 个是否能被 p 的前 j 个匹配
        dp[0][0] = true;
        for (int j = 1; j <= p.length(); ++j) if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 2];
        for (int i = 1; i <= s.length(); ++i) {
            for (int j = 1; j <= p.length(); ++j) {
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')
                    dp[i][j] = dp[i - 1][j - 1];
                else if (p.charAt(j - 1) == '*') {
                    if (s.charAt(i - 1) != p.charAt(j - 1 - 1) && p.charAt(j - 1 - 1) != '.')
                        dp[i][j] = dp[i][j - 2]; // '*'前的元素匹配不上 ex: s:###ab p:###c*
                    else // '*'前的元素可以匹配
                    dp[i][j] =
                                dp[i][j - 2] // 匹配0个，跳过'#*' ex: s:###cb p:###cc*
                                        || dp[i - 1][j]; // 匹配多个 ex: s:###cccb p:###c*
                } else dp[i][j] = false;
            }
        }
        return dp[s.length()][p.length()];
    }

    // 回溯：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
    // ps：回溯时用下标比截取string子串更省时
    public static boolean isMatch(String s, String p) {
        if (p.isEmpty()) return s.isEmpty();
        boolean firstMatch =
                (!s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')); // 匹配双方首元素
        if (p.length() >= 2 && p.charAt(1) == '*')
            return (isMatch(s, p.substring(2)) // '*'前的元素未被匹配 ex: s:###ab p:###c*
                    || firstMatch
                            && isMatch(
                                    s.substring(1),
                                    p)); // '*'前的元素被匹配，保持p不变，调用isMatch比较s后续的元素 ex: s:###aab p:###a*
        else return firstMatch && isMatch(s.substring(1), p.substring(1));
    }

    // 动态规划 + 回溯
    public static boolean isMatch2(String s, String p) {
        int[][] memo = new int[s.length() + 1][p.length() + 1];
        return dp(s, p, 0, 0, memo);
    }

    private static boolean dp(String s, String p, int i, int j, int[][] memo) {
        if (j >= p.length()) return i >= s.length();
        if (memo[i][j] > 0) return memo[i][j] == 1; // 已尝试匹配，直接返回

        boolean firstMatch = (i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.'));
        boolean res;
        if (j < p.length() - 1 && p.charAt(j + 1) == '*')
            res = dp(s, p, i, j + 2, memo) || firstMatch && dp(s, p, i + 1, j, memo);
        else res = firstMatch && dp(s, p, i + 1, j + 1, memo);
        memo[i][j] = res ? 1 : 2;
        return res;
    }
}
